class Solution
{
public:
    vector<bool> isArraySpecial(vector<int> &nums, vector<vector<int>> &queries)
    {
        vector<int> starts{0};
        for (int i = 1; i < nums.size(); ++i)
        {
            if (!((nums[i] & 1) ^ (nums[i - 1] & 1)))
            {
                starts.push_back(i);
            }
        }

        vector<bool> ans;
        for (auto &query : queries)
        {
            auto startPos = upper_bound(starts.begin(), starts.end(), query[0]);
            if (startPos == starts.end() || *startPos > query[1])
            {
                ans.push_back(true);
            }
            else
            {
                ans.push_back(false);
            }
        }
        return ans;
    }
};